package com.leo.datastruct.sort;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月02日
 */
public class MergeSort extends Sortable {

    public MergeSort(String sortMethodName) {
        super(sortMethodName);
    }

    @Override
    public void sort(int[] s) {
        sort1(s, 0, s.length-1);
    }

    private void sort1(int[] s, int start, int end){
        if (start < end){
            int mid = (start+end)/2;
            sort1(s, start, mid);
            sort1(s, mid+1, end);
            merge(s, start, mid, end);
        }
    }

    private void merge(int[] s, int start, int mid, int end){
        //暂存合并后的数组内容
        int[] temp = new int[end-start+1];
        //前部分指针
        int i = start;
        //后部分指针
        int j = mid+1;
        //合并后的数组指针
        int k = 0;
        while (i<=mid && j<=end){
            if (s[i] > s[j]){
                temp[k++] = s[j++];
            }else {
                temp[k++] = s[i++];
            }
        }
        while (i<=mid){ temp[k++] = s[i++];}
        while (j<=end){ temp[k++] = s[j++];}

        System.arraycopy(temp, 0, s, start, temp.length);
    }

    public static void main(String[] args) {
        Sortable a = new MergeSort("2-归并排序");
        a.testSort(new int[]{49,38,65,97,76,13,27,49,78,34,12,64,1});
    }
}
